#include <algorithm>
#include "Graph.h"

using namespace std;

Graph::Graph(std::vector<std::string> words) :
        index2nodes(vector<vector<Node> >(26)) {
    int len = (int) words.size();
    for (int i = 0; i < len; i++) {
        std::string s = words.at(i);
        Node node = Node(s);
        index2nodes.at(node.head - 'a').push_back(node);
    }
}

bool Graph::hasCircle() {
    for (int i = 0; i < 26; i++) {
        for (Node &node: index2nodes.at(i)) {
            if (!node.checkVisit) {
                if (checkCircle(node))return true;
            }
        }
    }
    return false;
}


int Graph::genAllChain(std::vector<std::string> &result) {

    for (int i = 0; i < 26; i++) {
        for (Node &node: index2nodes.at(i)) {
            dfsGenAll(result, node);
        }
    }

    return 0;
}

//void Graph::dfsGenAll(std::vector<std::string> &result,Node &node, char head, char tail) {
//    if (node.visit) return;
//    node.visit = VISITING;
//    node.chains.emplace_back(node.str);
//    for(Node& i:index2nodes[node.tail-'a']){
//        std::vector<std::string> temp;
//        if (!i.visit){
//            dfsGenAll(result,i,head,tail);
//
//        }
//        temp = i.chains;
//
//        for(std::string& s:temp){
//            node.chains.emplace_back(node.str+" "+s);
//            if((head=='\0'||node.head==head)&&(tail=='\0'||s.back()==tail)) result.emplace_back(node.str+" "+s);
//        }
//    }
//}
void Graph::dfsGenAll(std::vector<std::string> &result, Node &node) {
    if (node.visit) return;
    node.visit = VISITING;
    node.chains.emplace_back(node.str);
    for (Node &i: index2nodes[node.tail - 'a']) {
        if(node.str == i.str) continue;
        std::vector<std::string> temp;
        if (!i.visit) {
            dfsGenAll(result, i);

        }
        temp = i.chains;

        for (std::string &s: temp) {
            node.chains.emplace_back(node.str + " " + s);
            result.emplace_back(node.str + " " + s);
        }
    }
}

bool Graph::checkCircle(Node &node) {
    node.checkVisit = VISITING;
    for (Node &i: index2nodes[node.tail - 'a']) {
        if (node.str == i.str) continue;
        if (i.checkVisit == VISITING) return true;
        if (i.checkVisit == NOT_VISIT) {
            if (checkCircle(i)) return true;
        }
    }

    node.checkVisit = VISITED;
    return false;


}


int Graph::genMaxWordChain(vector<std::string> &result, char head, char tail) {
    int max = 0;
    if (head == '\0') {
        for (int i = 0; i < 26; i++) {
            for (Node &node: index2nodes.at(i)) {
                if (!node.visit) {
                    dfsGenMaxWordChain(node, tail);
                    if (max < node.max) {
                        result = node.chains;
                        max = node.max;
                    }
                }
            }
        }
    } else {
        for (Node &node: index2nodes.at(head - 'a')) {
            if (!node.visit) {
                dfsGenMaxWordChain(node, tail);
                if (max < node.max) {
                    result = node.chains;
                    max = node.max;
                }
            }
        }
    }
    if (result.size()==1) {
        result.clear();
        return 0;
    }

    std::reverse(result.begin(), result.end());
    return max;
}

void Graph::dfsGenMaxWordChain(Node &node, char tail) {
    if (node.visit) return;
    node.visit = VISITING;
//    node.chains.emplace_back(node.str);
    Node *maxNode = nullptr;
    int max = 0;
    for (Node &i: index2nodes[node.tail - 'a']) {
        if(node.str == i.str) continue;
        if (!i.visit) {
            dfsGenMaxWordChain(i, tail);

        }
        if (max < i.max) {
            max = i.max;
            maxNode = &i;
        }
    }
    if (max > 0) {
        node.chains.assign(maxNode->chains.begin(), maxNode->chains.end());
        node.chains.emplace_back(node.str);
        node.max = max + 1;
    } else if (tail == '\0' || node.tail == tail) {
        node.chains.emplace_back(node.str);
        node.max = 1;
    }


}


int Graph::genMaxCharChain(vector<std::string> &result, char head, char tail) {
    int max = 0;
    if (head == '\0') {
        for (int i = 0; i < 26; i++) {
            for (Node &node: index2nodes.at(i)) {
                if (!node.visit) {
                    dfsGenMaxCharChain(node, tail);
                    if (max < node.max) {
                        result = node.chains;
                        max = node.max;
                    }
                }
            }
        }
    } else {
        for (Node &node: index2nodes.at(head - 'a')) {
            if (!node.visit) {
                dfsGenMaxCharChain(node, tail);
                if (max < node.max) {
                    result = node.chains;
                    max = node.max;
                }
            }
        }
    }
    if (result.size()==1) {
        result.clear();
        return 0;
    }
    std::reverse(result.begin(), result.end());
    return max;
}

void Graph::dfsGenMaxCharChain(Node &node, char tail) {
    if (node.visit) return;
    node.visit = VISITING;
//    node.chains.emplace_back(node.str);
    Node *maxNode = nullptr;
    int max = 0;
    for (Node &i: index2nodes[node.tail - 'a']) {
        if(node.str == i.str) continue;
        if (!i.visit) {
            dfsGenMaxCharChain(i, tail);

        }
        if (max < i.max) {
            max = i.max;
            maxNode = &i;
        }
    }
    if (max > 0) {
        node.chains.assign(maxNode->chains.begin(), maxNode->chains.end());
        node.chains.emplace_back(node.str);
        node.max = max + (int) node.str.length();
    } else if (tail == '\0' || node.tail == tail) {
        node.chains.emplace_back(node.str);
        node.max = (int) node.str.length();
    }

}

int Graph::genMaxWordChainNotSame(vector<std::string> &result) {
    int max = 0;
    for (int i = 0; i < 26; i++) {
        for (Node &node: index2nodes.at(i)) {

            dfsGenMaxWordChainNotSame(node);
            if (max < node.max) {
                result = node.chains;
                max = node.max;
            }

        }
    }
    if (result.size()==1) {
        result.clear();
        return 0;
    }
    std::reverse(result.begin(), result.end());
    return max;
}

void Graph::dfsGenMaxWordChainNotSame(Node &node) {
    if (node.visit) return;
    node.visit = VISITING;
//    node.chains.emplace_back(node.str);
    Node *maxNode = nullptr;
    int max = 0;
    for (Node &i: index2nodes[node.tail - 'a']) {
        if(node.str == i.str) continue;
        if (!i.visit) {
            dfsGenMaxWordChainNotSame(i);

        }
        if (max < i.max && (i.firstSet & 1 << (node.head - 'a')) == 0) {
            max = i.max;
            maxNode = &i;
        }
    }
    if (max > 0) {
        node.chains.assign(maxNode->chains.begin(), maxNode->chains.end());
        node.firstSet = maxNode->firstSet;

    }
    node.chains.emplace_back(node.str);
    node.max = max + 1;
    node.firstSet |= 1 << (node.head - 'a');
//    else if (tail=='\0'||node.tail == tail){
//        node.chains.emplace_back(node.str);
//        node.max = 1;
//    }
}

int Graph::genMaxWordChainWithCircle(vector<std::string> &result, char head, char tail) {
    int max = 0;
    if (head == '\0') {
        #pragma omp parallel for schedule(dynamic)
        for (int i = 0; i < 26; i++) {
            for (Node &node: index2nodes.at(i)) {
                vector<string> list;
                unordered_set<string> visited;
                int ret = dfsGenMaxWordChainWithCircle(list, node, tail,visited);
                if (max < ret) {
                    #pragma omp critical
                    {
                    result = list;
                    max = ret;
                    }
                }

            }
        }
    } else {
        auto &nodes = index2nodes[head - 'a'];
        int ub = nodes.size();
        #pragma omp parallel for
        for (int i = 0; i < ub; i++) {
            auto &node = nodes[i];
            vector<string> list;
            unordered_set<string> visited;
            int ret = dfsGenMaxWordChainWithCircle(list, node, tail,visited);
            if (max < ret) {
                #pragma omp critical
                {
                    result = list;
                    max = ret;
                }
            }

        }
    }
    if (result.size()==1) {
        result.clear();
        return 0;
    }
    std::reverse(result.begin(), result.end());
    return max;
}

int Graph::dfsGenMaxWordChainWithCircle(vector<std::string> &list, Node &node, char tail,std::unordered_set<std::string> &visited) {
//    node.visit = VISITING;
    visited.insert(node.str);
    vector<string> maxList;
    int max = 0;
    for (Node &i: index2nodes[node.tail - 'a']) {
        if (visited.find(i.str)==visited.end()) {
            vector<string> temp;
            int ret = dfsGenMaxWordChainWithCircle(temp, i, tail,visited);
            if (max < ret) {
                max = ret;
                maxList = temp;
            }
        }
    }
//    node.visit = NOT_VISIT;
    visited.erase(node.str);
    if (max > 0) {
        list = maxList;
        list.emplace_back(node.str);
        return max + 1;
    }
    else if (tail == '\0' || node.tail == tail){
        list.emplace_back(node.str);
        return 1;
    }
    return 0;
}

int Graph::genMaxCharChainWithCircle(vector<std::string> &result, char head, char tail) {
    int max = 0;
    if (head == '\0') {
        #pragma omp parallel for schedule(dynamic)
        for (int i = 0; i < 26; i++) {
            for (Node &node: index2nodes.at(i)) {
                vector<string> list;
                unordered_set<string> visited;
                int ret = dfsGenMaxCharChainWithCircle(list, node, tail,visited);
                if (max < ret) {
                    #pragma omp critical
                    {
                        result = list;
                        max = ret;
                    }
                }

            }
        }
    } else {
        auto &nodes = index2nodes[head - 'a'];
        int ub = nodes.size();
        #pragma omp parallel for
        for (int i = 0; i < ub; i++) {
            auto &node = nodes[i];
            vector<string> list;
            unordered_set<string> visited;
            int ret = dfsGenMaxCharChainWithCircle(list, node, tail,visited);
            if (max < ret) {
                #pragma omp critical
                {
                    result = list;
                    max = ret;
                }
            }

        }
    }
    if (result.size()==1) {
        result.clear();
        return 0;
    }
    std::reverse(result.begin(), result.end());
    return max;
}

int Graph::dfsGenMaxCharChainWithCircle(vector<std::string> &list, Node &node, char tail,std::unordered_set<std::string> &visited) {
//    node.visit = VISITING;
    visited.insert(node.str);
    vector<string> maxList;
    int max = 0;
    for (Node &i: index2nodes[node.tail - 'a']) {
        if (visited.find(i.str)==visited.end()) {
            vector<string> temp;
            int ret = dfsGenMaxWordChainWithCircle(temp, i, tail,visited);
            if (max < ret) {
                max = ret;
                maxList = temp;
            }
        }
    }
//    node.visit = NOT_VISIT;
    visited.erase(node.str);
    if (max > 0) {
        list = maxList;
        list.emplace_back(node.str);
        return max + (int) node.str.length();
    }
    else if (tail == '\0' || node.tail == tail){
        list.emplace_back(node.str);
        return (int) node.str.length();
    }
    return 0;
}





